/**
 *力扣嘉年华的花店中从左至右摆放了一排鲜花，记录于整型一维矩阵 flowers 中每个数字表示该位置所种鲜花的品种编号。你可以选择一段区间的鲜花做成插花，且不能丢弃。 在你选择的插花中，如果每一品种的鲜花数量都不超过 cnt 朵，那么我们认为这束插花是 「美观的」。
 *https://leetcode.cn/problems/1GxJYY/description/
 */
class BeautifulBouquet {
    public int beautifulBouquet(int[] flowers, int cnt) {
        long ret = 0;
        Map<Integer,Integer> map = new HashMap<>();
        int len = flowers.length;
        int left = 0;
        int right = 0;
        while(right < len) {
            int c = flowers[right];
            right++;
            map.put(c,map.getOrDefault(c,0)+1);
            while(map.get(c) > cnt) {
               if(map.containsKey(flowers[left])) {
                   map.put(flowers[left],map.getOrDefault(flowers[left],1)-1);
               }
               left++;
            }
            ret += (right - left);
        }
        return (int)ret;
    }
}